package algorithm;

import java.util.Stack;

/**
 * @author MaGuangQi
 * @description 用栈实现队列
 * 思路: 需要2个栈,一个输入栈,一个输出栈, push元素进输入栈
 * pop时,先把input元素复制到output,相当于把input反转了.然后从output弹出
 * 就实现了队列的功能 232题
 * https://leetcode-cn.com/problems/implement-queue-using-stacks/
 * @date 2020-06-15 18:23
 **/
public class StackGenQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;
    public StackGenQueue() {
        input = new Stack<Integer>();
        output =new Stack<Integer>();
    }

    /**
     * 新增元素
     */
    public void push(int element) {
        input.push(element);
    }

    /**
     * 出栈
     */
    public int pop() {
        if (output.empty() && input.empty()) {
            throw new RuntimeException("没有元素");
        }
        //ouput不空,直接输出栈顶元素
        if (!output.empty()) {
            return output.pop();
        }
        //把input内容复制到output
        while (!input.empty()) {
            Integer value = input.pop();
            output.push(value);
        }
        return output.pop();
    }

    /**
     * 返回队列首部的元素。
     */
    public int peek() {
        if (output.empty() && input.empty()) {
            throw new RuntimeException("没有元素");
        }
        //ouput不空,直接输出栈顶元素
        if (!output.empty()) {
            return output.peek();
        }
        //把input内容复制到output
        while (!input.empty()) {
            Integer value = input.pop();
            output.push(value);
        }
        return output.peek();
    }

    /**
     * 判断队列是否为空
     */
    public boolean empty() {
        return input.empty() && output.empty();
    }

    public static void main(String[] args) {
        StackGenQueue stackGenQueue = new StackGenQueue();
        stackGenQueue.push(1);
        stackGenQueue.push(2);
        stackGenQueue.push(3);
        stackGenQueue.push(4);
        System.out.println(stackGenQueue.peek());
        System.out.println(stackGenQueue.pop());
        System.out.println(stackGenQueue.pop());
        System.out.println(stackGenQueue.empty());
    }
}
